import time

def calcTime(func):
        '''
        函数修饰器, 用来计算各个排序算法的执行时间
        最终返回一个 list [temp, time_sum]
        '''
        def warpper (*args, **kwds):
            time_start = time.perf_counter()
            temp = func(*args, **kwds)
            time_end = time.perf_counter()
            time_sum = time_end - time_start
            return [temp, time_sum*1000]
        return warpper

class Solution:
    @calcTime
    def restoreIpAddresses(self, s: str):
        SEG_COUNT = 4
        ans = list()
        segments = [0] * SEG_COUNT
        
        def dfs(segId: int, segStart: int):
            # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
            if segId == SEG_COUNT:
                if segStart == len(s):
                    ipAddr = ".".join(str(seg) for seg in segments)
                    ans.append(ipAddr)
                return
            
            # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
            if segStart == len(s):
                return

            # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
            if s[segStart] == "0":
                segments[segId] = 0
                dfs(segId + 1, segStart + 1)
            
            # 一般情况，枚举每一种可能性并递归
            addr = 0
            for segEnd in range(segStart, len(s)):
                addr = addr * 10 + (ord(s[segEnd]) - ord("0"))
                if 0 < addr <= 0xFF:
                    segments[segId] = addr
                    dfs(segId + 1, segEnd + 1)
                else:
                    break

        dfs(0, 0)
        return ans


if __name__ == "__main__":
    a = Solution()
    print(a.restoreIpAddresses("101023"))